% *******************************************************************************
%%  Copyright by Wenliang Du.                                                 %%
%%  This work is licensed under the Creative Commons                         %%
%%  Attribution-NonCommercial-ShareAlike 4.0 International License.            %%
%%  To view a copy of this license, visit                                     %%
%%  http://creativecommons.org/licenses/by-nc-sa/4.0/.                         %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% *******************************************
% SECTION
% *******************************************
\section{代码编译}
\label{sidechannel:sec:compilation}

\paragraph{\textbf{针对Ubuntu 16.04操作系统}}
对于我们的大部分任务，你需要在使用 \texttt{gcc} 编译代码时添加 \texttt{-march=native} 参数。该参数告诉编译器启用本地机器支持的所有指令子集。
例如，我们可以通过以下命令来编译 \texttt{myprog.c}：

\begin{lstlisting}
$ gcc -march=native -o myprog myprog.c
\end{lstlisting}

\paragraph{\textbf{针对Ubuntu 20.04操作系统}}
在Ubuntu 20.04操作系统中，添加 \texttt{-march=native} 参数可能会导致某些计算机出现错误。经过我们的调试努力，似乎这个选项已经不再需要了。
因此，如果你因为这个选项遇到了错误，请尝试不使用该选项来编译代码：

\begin{lstlisting}
$ gcc -o myprog myprog.c
\end{lstlisting}

% *******************************************
% SECTION
% ******************************************* 
\section{任务1和2：通过CPU缓存进行侧信道攻击}

Meltdown 和 Spectre 攻击都利用了 CPU 缓存作为侧信道来窃取受保护的秘密。这种侧信道技术称为 FLUSH+RELOAD~\cite{Yarom2014}。
我们将首先研究这种技术。这两个任务中开发的代码将作为后续任务的基础。

CPU缓存是一种硬件缓存，用于计算机中的 CPU 以减少访问主内存数据的平均成本（时间或能量）。从主内存访问数据要比从缓存中快得多。当数据从主内存读取时，通常会被 CPU 缓存，因此如果再次使用相同的数据，访问速度将变得更快。
因此，当 CPU 需要访问某些数据时，它会先查看其缓存。如果数据在缓存中（这称为缓存命中），则会直接从中获取数据；如果没有找到数据（这称为缺失），CPU 将去主内存获取数据。后者的花费时间明显更长。
大多数现代 CPU 都有 CPU 缓存。

\begin{figure}[htb]
\centering
\includegraphics[width=0.9\textwidth]{\sideChannelFigs/cachehitmiss.pdf}
\caption{缓存命中与缺失}
\label{sidechannel:fig:cachehitmiss}
\end{figure}

\subsection{任务1：从缓存读取数据与从内存读取数据的比较}

缓存存储器用于以更快的速度为高速处理器提供数据。缓存存储器比主内存快得多。
我们来看一下时间差异。以下代码（\texttt{CacheTime.c}）中，我们有一个大小为 \texttt{10*4096} 的数组。首先访问其两个元素 \texttt{array[3*4096]} 和 \texttt{array[7*4096]}。
因此，包含这两个元素的页面将被缓存。然后我们从 \texttt{array[0*4096]} 到 \texttt{array[9*4096]} 读取元素并测量内存读取的时间。
图~\ref{sidechannel:fig:cachehitmiss} 显示了时间差异。在代码中，行 \ding{192} 在内存读取之前读取 CPU 的时间戳（TSC）计数器，而行 \ding{193} 在内存读取之后读取该计数器。
它们的差值是内存读取所花费的时间（以CPU周期为单位）。需要指出的是，缓存操作在缓存块级别进行，而不是字节级别。典型的缓存块大小为 64 字节。
我们使用 \texttt{array[k*4096]}，所以程序中使用的两个元素不会落在同一个缓存块里。

\begin{lstlisting}[caption=\texttt{CacheTime.c}]
#include <emmintrin.h>
#include <x86intrin.h>

uint8_t array[10*4096];

int main(int argc, const char **argv) {
  int junk=0;
  register uint64_t time1, time2;
  volatile uint8_t *addr;
  int i;
  
  // 初始化数组
  for(i=0; i<10; i++) array[i*4096]=1;

  // FLUSH 数组从 CPU 缓存中清除
  for(i=0; i<10; i++) _mm_clflush(&array[i*4096]);

  // 访问数组中的某些元素
  array[3*4096] = 100;
  array[7*4096] = 200;

  for(i=0; i<10; i++) {
    addr = &array[i*4096];
    time1 = __rdtscp(&junk);                  (*@\ding{192}@*)
    junk = *addr;
    time2 = __rdtscp(&junk) - time1;          (*@\ding{193}@*)
    printf("访问 array[%d*4096] 的时间：%d CPU周期\n",i, (int)time2);
  }
  return 0;
}
\end{lstlisting}

请使用 \texttt{gcc -march=native CacheTime.c} 编译上述代码，并运行它。数组的 \texttt{array[3*4096]} 和 \texttt{array[7*4096]} 是否比其他元素访问得更快？你需要至少运行该程序10次并描述你的观察结果。
从实验中，你需找到一个阈值来区分这些两种类型的内存访问：从缓存读取数据与从主内存读取数据。这个阈值对于后续任务是重要的。

% -------------------------------------------
% SUBSECTION
% ------------------------------------------- 
\subsection{任务2：使用缓存作为侧信道}

\begin{figure}[htb]
\centering
\includegraphics[width=0.9\textwidth]{\sideChannelFigs/flushreload.pdf}
\caption{侧信道攻击的示意图}
\label{sidechannel:fig:flushreload}
\end{figure}

本任务的目标是利用侧信道从受害者函数中提取被用作索引的秘密值。假设存在一个受害者函数，它使用秘密值作为索引来加载数组中的某些值。
并且假设该秘密值不能从外部访问。我们的目标是通过侧信道获取这个秘密值。我们将使用的技术称为 FLUSH+RELOAD~\cite{Yarom2014}（图 \ref{sidechannel:fig:flushreload} 说明了此技术，包括三个步骤）：

1. 将整个数组从缓存内存中清除，以确保数组没有被缓存。

2. 调用受害者函数，该函数根据秘密值访问数组中的一个元素。这将导致对应数组元素被缓存。

3. 清除整个数组并测量重新加载每个元素所需的时间。如果某个特定元素的加载时间快，则很可能这个元素已经存在于缓存中。
   这个元素必定是受害者函数所访问的那个元素，因此我们就可以确定秘密值是什么。

以下程序使用 FLUSH+RELOAD 技术来找出变量 \texttt{secret} 中包含的一个字节的秘密值。由于一个字节的秘密值有 256 种可能的值，
我们需要将每个值映射到数组中的一个元素上。
一种简单的方法是定义一个具有 256 个元素的数组（即，\texttt{array[256]}）。但是这并不起作用。缓存操作在块级别进行，而不是字节级别。
如果 \texttt{array[k]} 被访问，则包含该元素的一个内存块将被缓存。因此，\texttt{array[k]} 的相邻元素也将被缓存，
使得难以推断秘密值是什么。
为了解决这个问题，我们创建一个大小为 \texttt{256*4096} 字节的数组。在我们的重新加载步骤中使用的每个元素是 \texttt{array[k*4096]}。
因为 \texttt{4096} 大于典型的缓存块大小（64 字节），所以 \texttt{array[i*4096]} 和 \texttt{array[j*4096]} 不会同时在一个缓存块中。

由于 \texttt{array[0*4096]} 可能与相邻内存中的变量位于同一个缓存块内，可能因这些变量被缓存而意外地被缓存。因此，
我们应该避免在 FLUSH+RELOAD 方法中使用 \texttt{array[0*4096]}（其他索引 \texttt{k} 并没有这个问题）。
为了在程序中保持一致，我们对所有 \texttt{k} 值使用 \texttt{array[k*4096 + DELTA]}，其中 \texttt{DELTA} 定义为一个常量 1024。

\begin{lstlisting}[caption=\texttt{FlushReload.c}, label={sidechannel:list:flushreload}]
#include <emmintrin.h>
#include <x86intrin.h>

uint8_t array[256*4096];
int temp;
unsigned char secret = 94;

/* 假设缓存命中时间阈值 */
#define CACHE_HIT_THRESHOLD (80)
#define DELTA 1024

void flushSideChannel()
{
  int i;

  // 将数组写入内存，以防止触发 Copy-on-write
  for (i = 0; i < 256; i++) array[i*4096 + DELTA] = 1;

  // 清除缓存中的数组值
  for (i = 0; i < 256; i++) _mm_clflush(&array[i*4096 +DELTA]);
}

void victim()
{
  temp = array[secret*4096 + DELTA];
}

void reloadSideChannel() 
{
  int junk=0;
  register uint64_t time1, time2;
  volatile uint8_t *addr;
  int i;
  for(i = 0; i < 256; i++){
     addr = &array[i*4096 + DELTA];
     time1 = __rdtscp(&junk);
     junk = *addr;
     time2 = __rdtscp(&junk) - time1;
     if (time2 <= CACHE_HIT_THRESHOLD){
         printf("array[%d*4096 + %d] 在缓存中。\n", i, DELTA);
         printf("秘密值 = %d。\n",i);
     }
  }	
}

int main(int argc, const char **argv) 
{
  flushSideChannel();
  victim();
  reloadSideChannel();
  return (0);
}
\end{lstlisting}

请使用 \texttt{gcc} 编译上述程序并运行它（参见第~\ref{sidechannel:sec:compilation} 节以了解编译说明）。
需要注意的是，该技术并不完全准确，你可能无法每次都能观察到预期的输出结果。你应该至少运行该程序 20 次，并统计能够正确获取秘密值的次数。
你也可以根据任务1中得出的阈值调整 \texttt{CACHE_HIT_THRESHOLD}（此代码使用了80）。